import typing
from provate import TreeNode, preorder



# 题目：请完成一个函数，输入一个二叉树，输出它的镜像

# 可以考虑递归

def mirroe_recursive(root:TreeNode)->(TreeNode or None):
    if not root:
        return None

    if not root.leftchild and not root.rightchild:
        return root

    tmp = root.rightchild
    root.rightchild = root.leftchild
    root.leftchild = tmp

    if root.leftchild:
        mirroe_recursive(root.leftchild)

    if root.rightchild:
        mirroe_recursive(root.rightchild)


if __name__ == '__main__':
    root = TreeNode(8)
    root.leftchild = TreeNode(6)
    root.rightchild = TreeNode(10)
    root.leftchild.leftchild = TreeNode(5)
    root.leftchild.rightchild = TreeNode(7)
    root.rightchild.leftchild = TreeNode(9)
    root.rightchild.rightchild = TreeNode(11)

    preorder(root)
    mirroe_recursive(root)
    print()
    preorder(root)